背包問題

USACO有較全面的教學。

背包問題的核心就是選東西，根據選法判斷某個組合是否出現，或最大化這樣選的收益/代價。
通常背包問題的狀態數不會超過兩個，一邊是選中物品的數量，一邊是重量總和。

廢話不多說，直接上例題。

例題

Codeforces 837D

題目要你選 k 個數字並最大化乘積位數 0 的數量，很明顯，影響 0 的數量的只有 2,5。
我們可以直接用 5 的數量和選中多少數當作狀態，最大化狀態中 2 的數量。
計算答案時，枚舉 5 的數量，答案是最大的 min(5的數量,2的數量)，也就是 min(i, dp[k][i])。
解答

Codeforces 1097B

這題目 n 只有 15，可以暴力解，那如果 n 更大呢？
事實上，我們可以先假設所有角度都是順時針，如果要改其中一個角度方向，逆時針轉這個角度兩次。
也就是說 dp[sum % 360] = 0，改變 a[i] 方向就是 dp[j] = dp[(j + 2*a[i]) % 360]
在這些前提下做背包 DP，紀錄哪個角度可被組合出來，答案就是 dp[0]。

CSES 1159

乍看之下像經典背包，但物品數量比原本多很多。
如果硬幹會 TLE，怎麼辦呢。

這裡可以用到倍增的概念，把 k_i 分解成 2^1,2^2,...,2^m,k_i-2^(m+1)+1，其中 k_i >= 2^(m+1)+1。
新的物品 a[j] 表示一次取 2^j 個書，因此價格和頁數都要乘 2^j。
如此一來便可用 log2(k_i) 本書完成題目，
解答